package offer.zixing.chapter06;

import java.util.Stack;

/**
 * 直方图最大矩形面积
 *
 * 直方图是由排列在同一基线上的相邻柱子组成的图形。
 * 输入一个由非负数组成的数组，数组中的数字是直方图宽为1的柱子的高。求直方图中最大矩形的面积。
 * 例如，输入数组[3, 2, 5, 4, 6, 1, 4, 2]，它对应的直方图如图6.3所示。
 * 该直方图中最大的矩形的面积为12，如阴影部分所示。
 */
public class Test039 {
    public static void main(String[] args) {
        System.out.println(largestRectangleArea1(new int[]{3, 2, 5, 4, 6, 1, 4, 2}));
        System.out.println(largestRectangleArea2(new int[]{3, 2, 5, 4, 6, 1, 4, 2}));
        System.out.println(largestRectangleArea3(new int[]{3, 2, 5, 4, 6, 1, 4, 2}));
    }

    public static int largestRectangleArea1(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            int min = heights[i];
            for (int j = i; j < heights.length; j++) {
                min = Math.min(min, heights[j]);
                int area = min * (j - i + 1);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }

    public static int largestRectangleArea2(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        return helper(heights, 0, heights.length);
    }

    private static int helper(int[] heights, int start, int end) {
        if (start == end) {
            return 0;
        }
        if (start + 1 == end) {
            return heights[start];
        }
        int minIndex = start;
        for (int i = start + 1; i < end; i++) {
            if (heights[i] < heights[minIndex]) {
                minIndex = i;
            }
        }

        int area = (end - start) * heights[minIndex];
        int left = helper(heights, start, minIndex);
        int right = helper(heights, minIndex + 1, end);

        area = Math.max(area, left);
        return Math.max(area, right);
    }

    public static int largestRectangleArea3(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            int heigth = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, heigth * width);
        }
        return maxArea;
    }
}
